package org.example.struct.array;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author liyishan
 * @date 2024/8/8 10:13
 * @apiNote
 */

public class Test00748ShortestCompletingWord {
    public static void main(String[] args) {
        String licensePlate = "1s3 PSt";
        String[] words = {"step", "steps", "stripe", "stepple"};
        String res = shortestCompletingWord(licensePlate, words);
        System.out.println(res);
    }

    public static String shortestCompletingWord(String licensePlate, String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        int[] cnt = new int[26];
        for (int i = 0; i < licensePlate.length(); i++) {
            char ch = licensePlate.charAt(i);
            if (Character.isLetter(ch)) {
                cnt[Character.toLowerCase(ch) - 'a']++;
            }
        }
        for (int i = 0; i < words.length; i++) {
            int[] c = new int[26];
            for (int j = 0; j < words[i].length(); j++) {
                char ch = words[i].charAt(j);
                c[ch - 'a']++;
            }
            boolean ok = true;
            for (int j = 0; j < 26; j++) {
                if (c[j] < cnt[j]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                return words[i];
            }
        }
        return "";
    }
}
